package com.mango.leet.code.easy;

/**
 * 599. 两个列表的最小索引总和
 */

import java.util.*;

/**
 * 假设 Andy 和 Doris 想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。
 *
 * 你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个，则输出所有答案并且不考虑顺序。 你可以假设答案总是存在。
 *
 *  
 *
 * 示例 1:
 *
 * 输入: list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]，list2 = ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
 * 输出: ["Shogun"]
 * 解释: 他们唯一共同喜爱的餐厅是“Shogun”。
 * 示例 2:
 *
 * 输入:list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]，list2 = ["KFC", "Shogun", "Burger King"]
 * 输出: ["Shogun"]
 * 解释: 他们共同喜爱且具有最小索引和的餐厅是“Shogun”，它有最小的索引和1(0+1)。
 *  
 *
 * 提示:
 *
 * 1 <= list1.length, list2.length <= 1000
 * 1 <= list1[i].length, list2[i].length <= 30 
 * list1[i] 和 list2[i] 由空格 ' ' 和英文字母组成。
 * list1 的所有字符串都是 唯一 的。
 * list2 中的所有字符串都是 唯一 的。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/minimum-index-sum-of-two-lists
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LC599_MinimumIndexSumofTwoLists {
    public static void main(String[] args) {
        String[] list1 = {"Shogun", "Tapioca Express", "Burger King", "KFC"};
        String[] list2 = {"KFC","Shogun","Burger King"};
        System.out.println(Arrays.toString(new Solution().findRestaurant(list1,list2)));
    }
    static class Solution {
        public String[] findRestaurant(String[] list1, String[] list2) {
            // 先计算交集
            List<String> arr1 = Arrays.asList(list1);
            List<String> arr2 = Arrays.asList(list2);
            List<String> jiaoList = new ArrayList<>(arr1);
            jiaoList.retainAll(arr2);
            // 如果交集只有一个元素，则直接返回
            if(jiaoList.size() == 1){
                return new String[]{jiaoList.get(0)};
            }else{
                // 得到最小下标和，存到map中
                int minSum = Integer.MAX_VALUE;
                Map<Integer,List<String>> map = new HashMap<>();
                for(String str : jiaoList){
                    int sum = arr1.indexOf(str) + arr2.indexOf(str);
                    List list = map.getOrDefault(sum,new ArrayList<>());
                    list.add(str);
                    if(minSum > sum){
                        minSum = sum;
                        map.put(minSum,list);
                    }
                }
                return map.get(minSum).toArray(new String[map.get(minSum).size()]);
            }
        }
    }
}
